LinkedHashMap源码走读

LinkedHashMap是HashMap的子类，它同HashMap的不同之处在于HashMap存放元素是无序的，而LinkedHashMap通过维护一个所有Entry的双向链表，保证了元素迭代的顺序，该迭代顺序可以是插入顺序或者是访问顺序。

继承关系

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    /**
     * The head of the doubly linked list.
     */
    private transient Entry<K,V> header;
    ……
}

header用于双链表的链表头

HashMap的Entry结构

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    ...
}

private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
        ...
}

LinkedHashMap的Entry结构继承自HashMap的Entry，多了两个元素before和after,这两个元素就是用于双链表的来维护元素插入顺序的，它和next的作用不同，next是用于table数组上的链式存储结构的。

注意该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口。

put和get方法访问元素都会导致被访问的元素被移动到双链表的尾部，头部即最近最久未访问的元素。